package com.kobeliu.entity;

import java.util.*;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/2 9:26
 */

/**
 * 给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。
 *
 * 运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：
 *
 *     名次第 1 的运动员获金牌 "Gold Medal" 。
 *     名次第 2 的运动员获银牌 "Silver Medal" 。
 *     名次第 3 的运动员获铜牌 "Bronze Medal" 。
 *     从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。
 *
 * 使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。
 *
 * 示例 1：
 *
 * 输入：score = [5,4,3,2,1]
 * 输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"]
 * 解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。
 *
 * 示例 2：
 * 输入：score = [10,3,8,9,4]
 * 输出：["Gold Medal","5","Bronze Medal","Silver Medal","4"]
 * 解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。
 */
public class Demo_62_No506 {

    public static void main(String[] args) {
        int[] n = new int[]{5,4,3,2,1};
        System.out.println(findRelativeRanks(n).toString());
    }

    /**
     * 优先队列
     * 复杂度也一样，感觉稍微好点
     * @param score
     * @return
     */
    public static String[] findRelativeRanks(int[] score) {


        int len = score.length;
        PriorityQueue<int[]> queues = new PriorityQueue<>((o1, o2) -> o2[0]-o1[0]); //大根堆
        String[] strs = new String[len];
        for (int i = 0; i < len; i++) {
            queues.add(new int[]{score[i],i});
        }
        int[] poll;
        if(len>0){
            poll = queues.poll();
            strs[poll[1]] = "Gold Medal";
        }
        if(len>1){
            poll = queues.poll();
            strs[poll[1]] = "Silver Medal";
        }
        if(len>2){
            poll = queues.poll();
            strs[poll[1]] = "Bronze Medal";
        }
        if(len>3){
            int n = 3;
            while(n<len){
                poll = queues.poll();
                strs[poll[1]] = Integer.toString(++n);
            }
        }

        return strs;


    }

    /**
     * 由大向小排序 存入hashmap，然后用原数组一次对应
     * 时间复杂度 O(nlogn) 空间复杂度 O(n)
     * @param score
     * @return
     */
    public static String[] findRelativeRanks1(int[] score) {

        int len = score.length;
        int[] newScore = new int[len];
        for (int i = 0; i < len; i++) {
            newScore[i] = score[i];
        }
        Arrays.sort(newScore);
        Map<Integer,String> models = new HashMap<>();

        if(len>0){
            models.put(newScore[len-1],"Gold Medal");
        }
        if(len>1){
            models.put(newScore[len-2],"Silver Medal");
        }
        if(len>2){
            models.put(newScore[len-3],"Bronze Medal");
        }
        if(len>3){
            int num = 4;
            for (int i = newScore.length-4; i >-1 ; i--) {
                models.put(newScore[i],Integer.toString(num++));
            }
        }

        String[] strs = new String[len];
        for (int i = 0; i < len; i++) {
            strs[i] = models.get(score[i]);
        }

        return strs;


    }


}
